#include<stdio.h>
inline int read_fast()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

template<class T>void read(T &x)
{
	x=0;char ch=getchar();int f=0;
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x:x;
	return ;
}
